<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>disjoint set 并查集</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="disjoint-set-并查集">disjoint set 并查集</h1>
<h1 id="1-tushare-roy">1. tushare roy</h1>
<p>Disjoint Sets using union by rank and path compression Graph Algorithm</p>
<ul>
<li><a href="https://www.youtube.com/watch?v=ID00PMy0-vE&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=5">https://www.youtube.com/watch?v=ID00PMy0-vE&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=5</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/DisjointSet.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/DisjointSet.java</a></li>
</ul>
<pre><code class="language-java"><div><span class="hljs-keyword">package</span> com.interview.graph;

<span class="hljs-keyword">import</span> java.util.HashMap;
<span class="hljs-keyword">import</span> java.util.Map;

<span class="hljs-comment">/**
 * <span class="hljs-doctag">@author</span> tusroy
 * Date 06/20/2015
 *  
 * Video link - https://youtu.be/ID00PMy0-vE
 *  
 * Disjoint sets using path compression and union by rank
 * Supports 3 operations
 * 1) makeSet
 * 2) union
 * 3) findSet
 * 
 * For m operations and total n elements time complexity is O(m*f(n)) where f(n) is 
 * very slowly growing function. For most cases f(n) &lt;= 4 so effectively
 * total time will be O(m). Proof in Coreman book.
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">DisjointSet</span> </span>{

    <span class="hljs-keyword">private</span> Map&lt;Long, Node&gt; map = <span class="hljs-keyword">new</span> HashMap&lt;&gt;();

    <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span> </span>{
        <span class="hljs-keyword">long</span> data;
        Node parent;
        <span class="hljs-keyword">int</span> rank;
    }

    <span class="hljs-comment">/**
     * Create a set with only one element.
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">makeSet</span><span class="hljs-params">(<span class="hljs-keyword">long</span> data)</span> </span>{
        Node node = <span class="hljs-keyword">new</span> Node();
        node.data = data;
        node.parent = node;
        node.rank = <span class="hljs-number">0</span>;
        map.put(data, node);
    }

    <span class="hljs-comment">/**
     * Combines two sets together to one.
     * Does union by rank
     *
     * <span class="hljs-doctag">@return</span> true if data1 and data2 are in different set before union else false.
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">union</span><span class="hljs-params">(<span class="hljs-keyword">long</span> data1, <span class="hljs-keyword">long</span> data2)</span> </span>{
        Node node1 = map.get(data1);
        Node node2 = map.get(data2);

        Node parent1 = findSet(node1);
        Node parent2 = findSet(node2);

        <span class="hljs-comment">//if they are part of same set do nothing</span>
        <span class="hljs-keyword">if</span> (parent1.data == parent2.data) {
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">false</span>;
        }

        <span class="hljs-comment">//else whoever's rank is higher becomes parent of other</span>
        <span class="hljs-keyword">if</span> (parent1.rank &gt;= parent2.rank) {
            <span class="hljs-comment">//increment rank only if both sets have same rank</span>
            parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank + <span class="hljs-number">1</span> : parent1.rank;
            parent2.parent = parent1;
        } <span class="hljs-keyword">else</span> {
            parent1.parent = parent2;
        }
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">true</span>;
    }

    <span class="hljs-comment">/**
     * Finds the representative of this set
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">long</span> <span class="hljs-title">findSet</span><span class="hljs-params">(<span class="hljs-keyword">long</span> data)</span> </span>{
        <span class="hljs-keyword">return</span> findSet(map.get(data)).data;
    }

    <span class="hljs-comment">/**
     * Find the representative recursively and does path
     * compression as well.
     */</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> Node <span class="hljs-title">findSet</span><span class="hljs-params">(Node node)</span> </span>{
        Node parent = node.parent;
        <span class="hljs-keyword">if</span> (parent == node) {
            <span class="hljs-keyword">return</span> parent;
        }
        node.parent = findSet(node.parent);
        <span class="hljs-keyword">return</span> node.parent;
    }

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span> </span>{
        DisjointSet ds = <span class="hljs-keyword">new</span> DisjointSet();
        ds.makeSet(<span class="hljs-number">1</span>);
        ds.makeSet(<span class="hljs-number">2</span>);
        ds.makeSet(<span class="hljs-number">3</span>);
        ds.makeSet(<span class="hljs-number">4</span>);
        ds.makeSet(<span class="hljs-number">5</span>);
        ds.makeSet(<span class="hljs-number">6</span>);
        ds.makeSet(<span class="hljs-number">7</span>);

        ds.union(<span class="hljs-number">1</span>, <span class="hljs-number">2</span>);
        ds.union(<span class="hljs-number">2</span>, <span class="hljs-number">3</span>);
        ds.union(<span class="hljs-number">4</span>, <span class="hljs-number">5</span>);
        ds.union(<span class="hljs-number">6</span>, <span class="hljs-number">7</span>);
        ds.union(<span class="hljs-number">5</span>, <span class="hljs-number">6</span>);
        ds.union(<span class="hljs-number">3</span>, <span class="hljs-number">7</span>);

        System.out.println(ds.findSet(<span class="hljs-number">1</span>));
        System.out.println(ds.findSet(<span class="hljs-number">2</span>));
        System.out.println(ds.findSet(<span class="hljs-number">3</span>));
        System.out.println(ds.findSet(<span class="hljs-number">4</span>));
        System.out.println(ds.findSet(<span class="hljs-number">5</span>));
        System.out.println(ds.findSet(<span class="hljs-number">6</span>));
        System.out.println(ds.findSet(<span class="hljs-number">7</span>));
    }
}
</div></code></pre>
<h1 id="2-labuladong">2. labuladong</h1>
<ul>
<li>
<p><a href="https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/UnionFind%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3.html">https://github.com/labuladong/fucking-algorithm/blob/master/算法思维系列/UnionFind算法详解.md</a></p>
</li>
<li>
<p><a href="https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/UnionFind%E7%AE%97%E6%B3%95%E5%BA%94%E7%94%A8.html">https://github.com/labuladong/fucking-algorithm/blob/master/算法思维系列/UnionFind算法应用.md</a></p>
</li>
<li>
<p><a href="https://labuladong.gitbook.io/algo/gao-pin-mian-shi-xi-lie/unionfind-suan-fa-xiang-jie">https://labuladong.gitbook.io/algo/gao-pin-mian-shi-xi-lie/unionfind-suan-fa-xiang-jie</a></p>
</li>
<li>
<p><a href="https://labuladong.gitbook.io/algo/gao-pin-mian-shi-xi-lie/unionfind-suan-fa-ying-yong">https://labuladong.gitbook.io/algo/gao-pin-mian-shi-xi-lie/unionfind-suan-fa-ying-yong</a></p>
</li>
</ul>
<h1 id="3-my-note">3. my note</h1>
<ul>
<li><a href="https://blog.csdn.net/niushuai666/article/details/6662911">https://blog.csdn.net/niushuai666/article/details/6662911</a></li>
<li><a href="https://blog.csdn.net/qq_19782019/article/details/78916595">https://blog.csdn.net/qq_19782019/article/details/78916595</a></li>
</ul>
<p>并查集由一个整数型的数组和两个函数构成。数组pre[]记录了每个点的前导点是什么，函数find是查找，join是合并。</p>
<pre><code class="language-java"><div><span class="hljs-keyword">int</span> pre[<span class="hljs-number">1000</span> ];
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">find</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x)</span>                                       <span class="hljs-comment">//查找根节点</span>
</span>{ 
    <span class="hljs-keyword">int</span> r=x;
    <span class="hljs-keyword">while</span> ( pre[r] != r )                           <span class="hljs-comment">//返回根节点 r</span>
          r=pre[r];
 
    <span class="hljs-keyword">int</span> i=x , j ;
    <span class="hljs-keyword">while</span>( i != r )                                   <span class="hljs-comment">//路径压缩</span>
    {
         j = pre[ i ]; 				<span class="hljs-comment">// 在改变上级之前用临时变量  j 记录下他的值 </span>
         pre[ i ]= r ; 				<span class="hljs-comment">//把上级改为根节点</span>
         i=j;
    }
    <span class="hljs-keyword">return</span> r ;
}


<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">join</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y)</span>                           <span class="hljs-comment">//判断x y是否连通，</span>
                                               <span class="hljs-comment">//如果已经连通，就不用管了 如果不连通，就把它们所在的连通分支合并起,</span>
</span>{
    <span class="hljs-keyword">int</span> fx=find(x),fy=find(y);
    <span class="hljs-keyword">if</span>(fx!=fy)
        pre[fx ]=fy;
}
</div></code></pre>
<p>在merge的时候，可以基于rank或者size 进行优化。</p>
<ul>
<li>将rank(level层数低的) 合并到 rank(level高的)</li>
<li>将size小的合并到size大的</li>
</ul>
<p>关于路径压缩的优化</p>
<p>前面的路径压缩代码太长了，虽然容易懂。 看了labuladong的文章 “Union-Find并查集算法介绍”以后， 发现路径压缩可以很简单, 但是这个压缩的质量不高。</p>
<pre><code class="language-java"><div><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">find</span><span class="hljs-params">(<span class="hljs-keyword">int</span> x)</span>                                       <span class="hljs-comment">//查找根节点</span>
</span>{ 
    <span class="hljs-keyword">int</span> r=x;
    <span class="hljs-keyword">while</span> (pre[r] != r )                           <span class="hljs-comment">//返回根节点 r</span>
    {
          pre[r] = pre[pre[r]]       <span class="hljs-comment">// 加这么一行即可</span>
          r=pre[r];
    } 
}
</div></code></pre>
<h1 id="4-相关题目">4. 相关题目:</h1>
<h2 id="41-lc-128-longest-consecutive-sequence">4.1 LC 128. Longest Consecutive Sequence</h2>
<ul>
<li><a href="https://leetcode.com/problems/longest-consecutive-sequence/">https://leetcode.com/problems/longest-consecutive-sequence/</a></li>
</ul>
<p>Given an unsorted array of integers, find the length of the longest consecutive elements sequence.</p>
<p>Your algorithm should run in O(n) complexity.</p>
<p>Example:</p>
<pre><code><code><div>Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
</div></code></code></pre>
<p>union find</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestConsecutive</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        
        father = {}
        father_size = {}

        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_find</span><span class="hljs-params">(num)</span>:</span>
            <span class="hljs-keyword">while</span> father[num] != num:
                father[num] = father[father[num]]
                num = father[num]
            <span class="hljs-keyword">return</span> num
        
        <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
            <span class="hljs-keyword">if</span> num <span class="hljs-keyword">in</span> father: <span class="hljs-comment"># for duplicated elment case [1,2,0,1]</span>
                <span class="hljs-keyword">continue</span>
            
            father[num] = num
            father_size[num] = <span class="hljs-number">1</span>
            
            left = num - <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> left <span class="hljs-keyword">in</span> father:
                left_father = _find(left)
                father[num] = left_father
                father_size[left_father] += father_size[num]
                
            right = num + <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> right <span class="hljs-keyword">in</span> father:
                right_father = _find(right)
                father[right_father] = father[num]
                father_size[father[num]] += father_size[right_father]
                
        <span class="hljs-keyword">return</span> max(father_size.values())
    
</div></code></pre>
<p>官方答案</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestConsecutive</span><span class="hljs-params">(self, nums)</span>:</span>
        longest_streak = <span class="hljs-number">0</span>

        <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
            current_num = num
            current_streak = <span class="hljs-number">1</span>

            <span class="hljs-keyword">while</span> current_num + <span class="hljs-number">1</span> <span class="hljs-keyword">in</span> nums:
                current_num += <span class="hljs-number">1</span>
                current_streak += <span class="hljs-number">1</span>

            longest_streak = max(longest_streak, current_streak)

        <span class="hljs-keyword">return</span> longest_streak
</div></code></pre>
<h2 id="42-lc-130被围绕的区域">4.2 LC 130.被围绕的区域</h2>
<ul>
<li><a href="https://leetcode.com/problems/surrounded-regions/">https://leetcode.com/problems/surrounded-regions/</a></li>
</ul>
<p>Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.</p>
<p>A region is captured by flipping all 'O's into 'X's in that surrounded region.</p>
<p>Example:</p>
<pre><code><code><div>X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X
</div></code></code></pre>
<p>Explanation:</p>
<p>Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.</p>
<h3 id="union-find">union-find</h3>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">solve</span><span class="hljs-params">(self, board: List[List[str]])</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        <span class="hljs-string">"""
        Do not return anything, modify board in-place instead.
        """</span>
        <span class="hljs-comment"># union search/ disjoint set</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> board <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> board[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span>
        m = len(board)
        n = len(board[<span class="hljs-number">0</span>])

        root = {}
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_find</span><span class="hljs-params">(i, j)</span>:</span>
            i0, j0 = i, j
            <span class="hljs-keyword">while</span> (i0,j0) <span class="hljs-keyword">in</span> root:
                i0,j0 = root[(i0,j0)]
                
            i2, j2  = i, j
            <span class="hljs-keyword">while</span> (i2,j2) != (i0, j0):
                prei,prej = root[(i2, j2)]
                root[(i2, j2)] = (i0, j0)
                i2, j2 = prei, prej
                
            <span class="hljs-keyword">return</span> (i0,j0)
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_union</span><span class="hljs-params">(root1, root2)</span>:</span>
            <span class="hljs-keyword">if</span> root1 == root2:
                <span class="hljs-keyword">return</span>
            
            <span class="hljs-keyword">if</span> root1[<span class="hljs-number">0</span>] == <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> root1[<span class="hljs-number">0</span>] == m<span class="hljs-number">-1</span> <span class="hljs-keyword">or</span> root1[<span class="hljs-number">1</span>] == <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> root1[<span class="hljs-number">1</span>] == n<span class="hljs-number">-1</span>:
                root[root2] = root1
            <span class="hljs-keyword">else</span>:
                root[root1] = root2
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n):
                <span class="hljs-keyword">if</span> board[i][j] == <span class="hljs-string">"O"</span>:
                    <span class="hljs-keyword">for</span> dx,dy <span class="hljs-keyword">in</span> [(<span class="hljs-number">-1</span>,<span class="hljs-number">0</span>), (<span class="hljs-number">1</span>,<span class="hljs-number">0</span>), (<span class="hljs-number">0</span>,<span class="hljs-number">-1</span>), (<span class="hljs-number">0</span>,<span class="hljs-number">1</span>)]:
                        i2, j2 = i+dx, j+dy
                        <span class="hljs-keyword">if</span> i2 &lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> i2&gt;=m <span class="hljs-keyword">or</span> j2&lt;<span class="hljs-number">0</span> <span class="hljs-keyword">or</span> j2&gt;=n:
                            <span class="hljs-keyword">continue</span>
                        <span class="hljs-keyword">if</span> board[i2][j2] == <span class="hljs-string">"O"</span>:
                            root1 = _find(i,j)
                            root2 = _find(i2,j2)
                            _union(root1, root2)
                    
        <span class="hljs-comment">#print(_find(0,1))</span>
                    
        <span class="hljs-comment">#from pprint import pprint        </span>
        <span class="hljs-comment">#pprint(root)            </span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n):
                <span class="hljs-keyword">if</span> board[i][j] == <span class="hljs-string">"O"</span>:
                    r = _find(i,j)
                    <span class="hljs-comment">#print(f"{i} {j} : {r}")</span>
                    <span class="hljs-keyword">if</span> r[<span class="hljs-number">0</span>] == <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> r[<span class="hljs-number">0</span>] == m<span class="hljs-number">-1</span> <span class="hljs-keyword">or</span> r[<span class="hljs-number">1</span>] == <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> r[<span class="hljs-number">1</span>] == n<span class="hljs-number">-1</span>:
                        <span class="hljs-keyword">pass</span>
                    <span class="hljs-keyword">else</span>:
                        board[i][j] = <span class="hljs-string">"X"</span>
                                           
</div></code></pre>
<h3 id="dfs">dfs</h3>
<p>从边上开始搜索，将搜索到达的&quot;O&quot;转变为&quot;Z&quot;.  遍历完以后，将所有的&quot;O&quot;转为&quot;X&quot;, 所有的&quot;Z&quot;转为&quot;O&quot;</p>
<h2 id="43-lc-200-number-of-islands">4.3 LC 200. Number of Islands</h2>
<h2 id="44-lc-990等式方程的可满足性">4.4 LC 990.等式方程的可满足性</h2>
<ul>
<li><a href="https://leetcode.com/problems/satisfiability-of-equality-equations/">https://leetcode.com/problems/satisfiability-of-equality-equations/</a></li>
</ul>
<p>iven an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: &quot;a==b&quot; or &quot;a!=b&quot;.  Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.</p>
<p>Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.</p>
<p>Example 1:</p>
<pre><code><code><div>Input: [&quot;a==b&quot;,&quot;b!=a&quot;]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.  There is no way to assign the variables to satisfy both equations.
</div></code></code></pre>
<p>union find</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">equationsPossible</span><span class="hljs-params">(self, equations: List[str])</span> -&gt; bool:</span>
        fathers = {}
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_find</span><span class="hljs-params">(x)</span>:</span>
            <span class="hljs-keyword">if</span> x <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> fathers:
                fathers[x] = x
                <span class="hljs-keyword">return</span> x
            
            <span class="hljs-keyword">while</span> x != fathers[x]:
                fathers[x] = fathers[fathers[x]]
                x = fathers[x]
                
            <span class="hljs-keyword">return</span> x
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_merge</span><span class="hljs-params">(x, y)</span>:</span>
            root_x = _find(x)
            root_y = _find(y)
            <span class="hljs-keyword">if</span> root_x != root_y:
                fathers[root_x] = root_y
    
        <span class="hljs-keyword">for</span> equation <span class="hljs-keyword">in</span> equations:
            <span class="hljs-keyword">if</span> equation[<span class="hljs-number">1</span>] == <span class="hljs-string">"!"</span>:
                <span class="hljs-keyword">continue</span>
            x, y = equation.split(<span class="hljs-string">"=="</span>)
            _merge(x, y)
            
        <span class="hljs-keyword">for</span> equation <span class="hljs-keyword">in</span> equations:
            <span class="hljs-keyword">if</span> equation[<span class="hljs-number">1</span>] == <span class="hljs-string">"="</span>:
                <span class="hljs-keyword">continue</span>
            x, y = equation.split(<span class="hljs-string">"!="</span>)
            root_x = _find(x)
            root_y = _find(y)
            <span class="hljs-keyword">if</span> root_x == root_y:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
    
</div></code></pre>
<h2 id="45-lc-952-largest-component-size-by-common-factor">4.5 LC 952. Largest Component Size by Common Factor</h2>
<ul>
<li><a href="https://leetcode.com/problems/largest-component-size-by-common-factor/">https://leetcode.com/problems/largest-component-size-by-common-factor/</a></li>
</ul>
<p>Given a non-empty array of unique positive integers A, consider the following graph:</p>
<p>There are A.length nodes, labelled A[0] to A[A.length - 1];</p>
<p>There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.</p>
<p>Return the size of the largest connected component in the graph.</p>
<pre><code><code><div>Example 1:

Input: [4,6,15,35]
Output: 4

Example 2:

Input: [20,50,9,63]
Output: 2

Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8
</div></code></code></pre>
<p>我最开始的方案， 并查集 + 最大公约数,  算法是正确的，但是提交后会超时</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestComponentSize</span><span class="hljs-params">(self, A: List[int])</span> -&gt; int:</span>
        n = len(A)
        father = [<span class="hljs-number">-1</span>] * n
        size = [<span class="hljs-number">1</span>] * n
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">(i)</span>:</span>
            cur = i
            <span class="hljs-keyword">while</span> father[cur] != <span class="hljs-number">-1</span>:
                cur = father[cur]
            root = cur
            
            cur = i
            <span class="hljs-keyword">while</span> father[cur] != <span class="hljs-number">-1</span>:
                father0 = father[cur]
                father[cur] = root
                cur = father0
            <span class="hljs-keyword">return</span> root
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">union</span><span class="hljs-params">(i, j)</span>:</span>
            root1 = find(i)
            root2 = find(j)
            <span class="hljs-keyword">if</span> root1 != root2:
                father[root2] = root1
                size[root1] = size[root1] + size[root2]
            
            
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">common</span><span class="hljs-params">(v1, v2)</span>:</span>
            <span class="hljs-keyword">if</span> v1 &gt; v2:
                <span class="hljs-keyword">return</span> common(v2, v1)
            <span class="hljs-keyword">if</span> v1 == v2:
                <span class="hljs-keyword">return</span> v1
            
            <span class="hljs-keyword">if</span> v1 % <span class="hljs-number">2</span> == <span class="hljs-number">0</span> <span class="hljs-keyword">and</span> v2 % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-number">2</span> * common(v1//<span class="hljs-number">2</span>, v2//<span class="hljs-number">2</span>)  <span class="hljs-comment"># 其实这里可以直接return 2</span>
            <span class="hljs-keyword">elif</span> v1 % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">return</span> common(v1//<span class="hljs-number">2</span>, v2)
            <span class="hljs-keyword">elif</span> v2 % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">return</span> common(v1, v2//<span class="hljs-number">2</span>)
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">return</span> common(v1, v2-v1)
            
        
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i+<span class="hljs-number">1</span>, n):
                r = common(A[i], A[j])
                <span class="hljs-keyword">if</span> r &gt; <span class="hljs-number">1</span>:
                    union(i, j)
        <span class="hljs-comment">#print(f"father={father}")</span>
        <span class="hljs-comment">#print(f"size={size}")</span>
        <span class="hljs-keyword">return</span> max(size)
    
</div></code></pre>
<p>下面是看了标准答案的做法,  并查集 + 每个element的约数</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestComponentSize</span><span class="hljs-params">(self, A: List[int])</span> -&gt; int:</span>
        <span class="hljs-comment">#A.sort()</span>
        n = len(A)
        m = max(A)
        father = list(range(m+<span class="hljs-number">1</span>))
        size = [<span class="hljs-number">1</span>] * (m+<span class="hljs-number">1</span>)
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">(i)</span>:</span>
            cur = i
            <span class="hljs-keyword">while</span> father[cur] != cur:
                father[cur] = father[father[cur]]
                cur = father[cur]
            <span class="hljs-keyword">return</span> cur
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">union</span><span class="hljs-params">(i, j)</span>:</span>
            root1 = find(i)
            root2 = find(j)
            <span class="hljs-keyword">if</span> root1 == root2:
                <span class="hljs-keyword">return</span> root1
            
            <span class="hljs-keyword">if</span> size[root1] &gt; size[root2]:
                root1, root2 = root2, root1
            father[root1] = root2
            size[root2] += size[root1]

            
        <span class="hljs-keyword">for</span> a <span class="hljs-keyword">in</span> A:
            t = <span class="hljs-number">2</span>
            <span class="hljs-keyword">while</span> t*t &lt;= a:
                <span class="hljs-keyword">if</span> a % t == <span class="hljs-number">0</span>:
                    union(a, t)
                    union(a, a//t)
                t += <span class="hljs-number">1</span>
        
        dt = {}
        ans = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> a <span class="hljs-keyword">in</span> A:
            root = find(a)
            dt[root] = dt.get(root, <span class="hljs-number">0</span>) + <span class="hljs-number">1</span>
            ans = max(ans, dt[root])
            
        <span class="hljs-keyword">return</span> ans
                    
    
    
</div></code></pre>
<h2 id="46-lc-1632-rank-transform-of-a-matrix">4.6 LC 1632. Rank Transform of a Matrix</h2>
<ul>
<li><a href="https://leetcode.com/problems/rank-transform-of-a-matrix/">https://leetcode.com/problems/rank-transform-of-a-matrix/</a></li>
</ul>
<p>Given an m x n matrix, return a new matrix answer where answer[row][col] is the rank of matrix[row][col].</p>
<p>The rank is an integer that represents how large an element is compared to other elements. It is calculated using the following rules:</p>
<ul>
<li>If an element is the smallest element in its row and column, then its rank is 1.</li>
<li>If two elements p and q are in the same row or column, then:</li>
<li>If p &lt; q then rank(p) &lt; rank(q)</li>
<li>If p == q then rank(p) == rank(q)</li>
<li>If p &gt; q then rank(p) &gt; rank(q)</li>
<li>The rank should be as small as possible.</li>
<li>It is guaranteed that answer is unique under the given rules.</li>
</ul>
<pre><code><code><div>Example 1:
Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[2,3]]
Explanation:
The rank of matrix[0][0] is 1 because it is the smallest integer in its row and column.
The rank of matrix[0][1] is 2 because matrix[0][1] &gt; matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][0] is 2 because matrix[1][0] &gt; matrix[0][0] and matrix[0][0] is rank 1.
The rank of matrix[1][1] is 3 because matrix[1][1] &gt; matrix[0][1], matrix[1][1] &gt; matrix[1][0], and both matrix[0][1] and matrix[1][0] are rank 2.
Example 2:


Input: matrix = [[7,7],[7,7]]
Output: [[1,1],[1,1]]
Example 3:


Input: matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]
Output: [[4,2,3],[1,3,4],[5,1,6],[1,3,4]]
Example 4:


Input: matrix = [[7,3,6],[1,4,5],[9,8,2]]
Output: [[5,1,4],[1,2,3],[6,3,1]]
</div></code></code></pre>
<p>本题很复杂，即使看了答案也不好懂。 我这里记录一下lee215的并查集解法</p>
<ul>
<li><a href="https://leetcode.com/problems/rank-transform-of-a-matrix/discuss/909142/Python-Union-Find">https://leetcode.com/problems/rank-transform-of-a-matrix/discuss/909142/Python-Union-Find</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">matrixRankTransform</span><span class="hljs-params">(self, A)</span>:</span>
        n, m = len(A), len(A[<span class="hljs-number">0</span>])
        rank = [<span class="hljs-number">0</span>] * (m + n)  <span class="hljs-comment"># rank就是rowMax[:] + colMax[:]</span>
        d = collections.defaultdict(list)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> xrange(n):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> xrange(m):
                d[A[i][j]].append([i, j])

        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">(i)</span>:</span>
            <span class="hljs-keyword">if</span> p[i] != i:
                p[i] = find(p[i])
            <span class="hljs-keyword">return</span> p[i]

        <span class="hljs-keyword">for</span> a <span class="hljs-keyword">in</span> sorted(d):
            p = range(m + n)  <span class="hljs-comment"># 这里关于如何把有关联点的rank整合在一起，很值得借鉴。</span>
            rank2 = rank[:]
            <span class="hljs-keyword">for</span> i, j <span class="hljs-keyword">in</span> d[a]:
                i, j = find(i), find(j + n)
                p[i] = j
                rank2[j] = max(rank2[i], rank2[j])
            <span class="hljs-keyword">for</span> i, j <span class="hljs-keyword">in</span> d[a]:
                rank[i] = rank[j + n] = A[i][j] = rank2[find(i)] + <span class="hljs-number">1</span>
        <span class="hljs-keyword">return</span> A
</div></code></pre>
<p>上面代码的精华</p>
<ol>
<li>是用并查集把一些有关联的点合并在一起.</li>
<li>用输入参数当作输出参数返回。</li>
</ol>
<p>例如 测试用例</p>
<pre><code><code><div>[[1,2,6],
 [2,2,5],
 [3,8,2]]
</div></code></code></pre>
<p>前两行的2是有关联的， 第三行的2是独立的。</p>
<p>上面的代码有点不好懂，我把rank用Max_val来表示。 max_val[&quot;r1&quot;]是第一行的最大值， max_val[&quot;c0&quot;]是第一列的最大值</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">matrixRankTransform</span><span class="hljs-params">(self, matrix: List[List[int]])</span> -&gt; List[List[int]]:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> matrix <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> matrix[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>
        m = len(matrix)
        n = len(matrix[<span class="hljs-number">0</span>])
        
        

        d = collections.defaultdict(list)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n):
                d[matrix[i][j]].append([i, j])

        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">(node)</span>:</span>
            c = node
            <span class="hljs-keyword">while</span> c <span class="hljs-keyword">in</span> parent:
                c = parent[c]
                <span class="hljs-comment">#print(f"c={c}")</span>
            <span class="hljs-keyword">return</span> c
        
        max_val = defaultdict(int)
        ans = [[<span class="hljs-number">0</span>] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m)]
        <span class="hljs-keyword">for</span> a <span class="hljs-keyword">in</span> sorted(d):
            parent = {}
            <span class="hljs-keyword">for</span> i, j <span class="hljs-keyword">in</span> d[a]:
                root_i = find(<span class="hljs-string">f"r<span class="hljs-subst">{i}</span>"</span>) <span class="hljs-comment"># row_i -&gt; col_j</span>
                root_j = find(<span class="hljs-string">f"c<span class="hljs-subst">{j}</span>"</span>)
                <span class="hljs-keyword">if</span> root_i != root_j:
                    parent[root_i] = root_j
                    max_val[root_j] = max(max_val[root_j], max_val[root_i])

            <span class="hljs-comment">#print(f"max_val={max_val} parent={parent}")</span>
            max_val2 = copy.deepcopy(max_val)
            <span class="hljs-keyword">for</span> i, j <span class="hljs-keyword">in</span> d[a]:
                max_val[<span class="hljs-string">f"r<span class="hljs-subst">{i}</span>"</span>] = max_val[<span class="hljs-string">f"c<span class="hljs-subst">{j}</span>"</span>] = ans[i][j] = max_val2[find(<span class="hljs-string">f"c<span class="hljs-subst">{j}</span>"</span>)] + <span class="hljs-number">1</span>
            <span class="hljs-comment">#print(f"a={a} ans={ans}")</span>
        <span class="hljs-keyword">return</span> ans
</div></code></pre>

    </body>
    </html>